class Node:
    def __init__(self):
        self.isEnd = False
        self.children = {}


class WordDictionary:

    def __init__(self):
        self.root = Node()

    def addWord(self, word: str) -> None:
        cur = self.root
        for i in word:
            if i not in cur.children:
                node = Node()
                cur.children[i] = node
            cur = cur.children[i]

        cur.isEnd = True

    def search(self, word: str) -> bool:
        cur = self.root
        return self._search_help(word, self.root)

    def _search_help(self, word: str, cur: Node) -> bool:
        if word == '':
            return cur.isEnd

        cur
        for i in word:
            if i == ".":
                for j in cur.children:
                    if self._search_help(word[word.find(i) + 1:], cur.children[j]):
                        return True
                return False
            else:
                if i not in cur.children:
                    return False
                else:
                    cur = cur.children[i]

        if cur.isEnd is True:
            return cur.isEnd
        return False


# Your WordDictionary object will be instantiated and called as such:
words = ["at", "and", "an", "add", "bad", "dad", "mad"]
search_words = ["bad","a", "b..", ".", ".ad", "b.."]
obj = WordDictionary()
for word in words:
    obj.addWord(word)
for word in search_words:
    obj.search(word)
    print(obj.search(word))
